package xyz.scootaloo.oj.offer;

/**
 * 未完成
 * @author flutterdash@qq.com
 * @since 2021/3/30 14:54
 */
public class P40b {

    public int[] getLeastNumbers(int[] arr, int k) {
        int len = arr.length;
        if (k == len)
            return new int[] {arr[0], arr[1], arr[2]};
        partitionArray(arr, 0, arr.length - 1, k);
        int[] res = new int[k];
        if (k >= 0)
            System.arraycopy(arr, 0, res, 0, k);
        return res;
    }

    private void partitionArray(int[] arr, int left, int right, int k) {
        int pos = partition(arr, left, right);
        if (k == pos)
            return;
        if (pos > k) {
            partitionArray(arr, left, pos - 1, k);
        } else {
            partitionArray(arr, pos + 1, right, k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        int pivot = arr[mid];
        int l = left;
        int r = right;
        while (l < r) {
            while (arr[l] < pivot) {
                l++;
            }
            while (arr[r] > pivot) {
                r--;
            }

            if (l >= r)
                break;
            swap(arr, l, r);
        }
        return r;
    }

    private void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] =  tmp;
    }

}
